package class01;

/**
 * 局部最小值问题
 * 在一个无序数组中，任意两个相邻的数都不相等
 * 定义：如果一个数小于其左右两侧的数，则称为局部最小值
 * 目标：找到任意一个局部最小值的位置
 */
public class Code06_BSAwesome {

	/**
	 * 寻找局部最小值的索引位置
	 * 使用二分查找的思想来优化时间复杂度
	 * 
	 * @param arr 输入数组，保证任意两个相邻元素不相等
	 * @return 返回局部最小值的索引，如果没有则返回-1
	 */
	// 课上的代码
	public static int getLessIndex(int[] arr) {
		// 边界条件检查：数组为空或长度为0
		if (arr == null || arr.length == 0) {
			return -1;
		}
		// 特殊情况1：只有一个元素或者第一个元素小于第二个元素，则第一个元素就是局部最小值
		if (arr.length == 1 || arr[0] < arr[1]) {
			return 0;
		}
		// 特殊情况2：最后一个元素小于倒数第二个元素，则最后一个元素是局部最小值
		if (arr[arr.length - 1] < arr[arr.length - 2]) {
			return arr.length - 1;
		}
		// 设置搜索范围，排除首尾已经检查过的元素
		int left = 1;
		int right = arr.length - 2;
		int mid = 0;
		// 二分查找过程
		while (left < right) {
			// 计算中间位置
			mid = (left + right) / 2;
			// 如果中间元素大于左边元素，说明左侧存在局部最小值
			if (arr[mid] > arr[mid - 1]) {
				right = mid - 1;
			// 如果中间元素大于右边元素，说明右侧存在局部最小值
			} else if (arr[mid] > arr[mid + 1]) {
				left = mid + 1;
			// 如果中间元素既小于左边也小于右边元素，则找到了局部最小值
			} else {
				return mid;
			}
		}
		return left;
	}

	/**
	 * 验证指定索引位置的元素是否为局部最小值
	 * 
	 * @param arr 数组
	 * @param index 待验证元素的索引
	 * @return 如果是局部最小值返回true，否则返回false
	 */
	// 验证得到的结果，是不是局部最小
	public static boolean isRight(int[] arr, int index) {
		// 空数组或单元素数组默认满足局部最小值条件
		if (arr.length <= 1) {
			return true;
		}
		// 检查第一个元素是否小于其右邻元素
		if (index == 0) {
			return arr[index] < arr[index + 1];
		}
		// 检查最后一个元素是否小于其左邻元素
		if (index == arr.length - 1) {
			return arr[index] < arr[index - 1];
		}
		// 检查中间元素是否同时小于左右相邻元素
		return arr[index] < arr[index - 1] && arr[index] < arr[index + 1];
	}

	/**
	 * 生成用于测试的随机数组，确保相邻元素不相等
	 * 
	 * @param maxSize 最大数组大小
	 * @param maxValue 数组元素的最大绝对值
	 * @return 生成的数组
	 */
	// 为了测试
	// 生成相邻不相等的数组
	public static int[] generateRandomArray(int maxSize, int maxValue) {
		// 创建指定大小的数组
		int[] arr = new int[(int) (Math.random() * maxSize) + 1];
		// 初始化第一个元素
		arr[0] = (int) (Math.random() * maxValue) - (int) (Math.random() * maxValue);
		// 依次初始化后续元素，确保与前一个元素不相等
		for (int i = 1; i < arr.length; i++) {
			do {
				arr[i] = (int) (Math.random() * maxValue) - (int) (Math.random() * maxValue);
			} while (arr[i] == arr[i - 1]);
		}
		return arr;
	}

	/**
	 * 主函数，用于测试算法正确性
	 * 进行大量随机测试验证算法是否正确
	 */
	// 为了测试
	public static void main(String[] args) {
		// 设置测试参数
		int testTime = 500000;
		int maxSize = 30;
		int maxValue = 100;
		System.out.println("测试开始");
		// 进行多次随机测试
		for (int i = 0; i < testTime; i++) {
			// 生成随机数组
			int[] arr = generateRandomArray(maxSize, maxValue);
			// 获取算法结果
			int ans = getLessIndex(arr);
			// 验证结果是否正确
			if (!isRight(arr, ans)) {
				System.out.println("出错了！");
				break;
			}
		}
		System.out.println("测试结束");
	}

}
